#include "ListDG.h"

#include <queue>

ListDG::Edge::Edge(Object_ptr from, Object_ptr to)
{
  this->from = from;
  this->to = to;
}

/*
 * 创建图(用已提供的矩阵)
 *
 * 参数说明：
 *     vexs  -- 顶点数组
 *     edges -- 边数组
 */
ListDG::ListDG(Object_list_ptr vexs, std::shared_ptr<std::list<std::shared_ptr<Edge>>> edges)
{
  // 初始化"顶点数"和"边数"
  int vlen = vexs->size();
  int elen = edges->size();

  // 初始化"顶点"
  // mVexs = new ArrayList<std::shared_ptr<VNode>>();
  mVexs = std::make_shared<std::list<std::shared_ptr<VNode>>>();
  auto it = vexs->begin();
  for (int i = 0; i < vlen; i++)
  {
    // 新建VNode
    std::shared_ptr<VNode> vnode = std::shared_ptr<VNode>(new VNode());
    std::advance(it, i);
    vnode->data = (*it);
    vnode->firstEdge = NULL;
    // 将vnode添加到数组mVexs中
    mVexs->push_back(vnode);
  }

  // 初始化"边"
  auto ite = edges->begin();
  auto itm = mVexs->begin();
  for (int i = 0; i < elen; i++)
  {
    // 读取边的起始顶点和结束顶点
    std::advance(ite, i);
    Object_ptr c1 = (*ite)->from;
    Object_ptr c2 = (*ite)->to;
    // 读取边的起始顶点和结束顶点
    int p1 = getPosition((*ite)->from);
    int p2 = getPosition((*ite)->to);

    // 初始化node1
    ENode *node1 = new ENode();
    node1->ivex = p2;
    // 将node1链接到"p1所在链表的末尾"
    std::advance(itm, p1);
    if ((*itm)->firstEdge == NULL)
    {
      (*itm)->firstEdge = node1;
    }
    else
    {
      linkLast((*itm)->firstEdge, node1);
    }
  }
}

/*
 * 将node节点链接到list的最后
 */
void ListDG::linkLast(ENode *list, ENode *node)
{
  ENode *p = list;

  while (p->nextEdge != NULL)
  {
    p = p->nextEdge;
  }
  p->nextEdge = node;
}

/*
 * 返回ch位置
 */
int ListDG::getPosition(Object_ptr ch)
{
  auto itm = mVexs->begin();
  for (int i = 0; i < mVexs->size(); i++)
  {
    std::advance(itm, i);
    if ((*itm)->data == ch)
    {
      return i;
    }
  }
  return -1;
}

/*
 * 深度优先搜索遍历图的递归实现
 */
void ListDG::DFS(int i, bool visited[])
{
  ENode *node;

  visited[i] = true;
  auto itm = mVexs->begin();
  std::advance(itm, i);
  node = (*itm)->firstEdge;
  while (node != NULL)
  {
    if (!visited[node->ivex])
    {
      DFS(node->ivex, visited);
    }
    node = node->nextEdge;
  }
}

/*
 * 深度优先搜索遍历图
 */
void ListDG::DFS()
{
  bool visited[mVexs->size()]; // 顶点访问标记

  // 初始化所有顶点都没有被访问
  for (int i = 0; i < mVexs->size(); i++)
  {
    visited[i] = false;
  }

  for (int i = 0; i < mVexs->size(); i++)
  {
    if (!visited[i])
    {
      DFS(i, visited);
    }
  }
}

/*
 * 广度优先搜索（类似于树的层次遍历）
 */
void ListDG::BFS()
{
  int head = 0;
  int rear = 0;
  int queue[mVexs->size()];    // 辅组队列
  bool visited[mVexs->size()]; // 顶点访问标记

  for (int i = 0; i < mVexs->size(); i++)
  {
    visited[i] = false;
  }

  for (int i = 0; i < mVexs->size(); i++)
  {
    if (!visited[i])
    {
      visited[i] = true;
      // System->out->printf("%c ", mVexs->get(i)->data);
      queue[rear++] = i; // 入队列
    }

    auto itm = mVexs->begin();
    while (head != rear)
    {
      int j = queue[head++]; // 出队列
      std::advance(itm, j);
      ENode *node = (*itm)->firstEdge;
      while (node != NULL)
      {
        int k = node->ivex;
        if (!visited[k])
        {
          visited[k] = true;
          // System->out->printf("%c ", mVexs->get(k)->data);
          queue[rear++] = k;
        }
        node = node->nextEdge;
      }
    }
  }
}

/*
 * 打印矩阵队列图
 */
void ListDG::print()
{
  // System->out->printf("== std::list Graph:\n");
  auto itm = mVexs->begin();
  for (int i = 0; i < mVexs->size(); i++)
  {
    // System->out->printf("%d(%c): ", i, mVexs->get(i)->data);
    std::advance(itm, i);
    ENode *node = (*itm)->firstEdge;
    while (node != NULL)
    {
      // System->out->printf("%d(%c) ", node->ivex, mVexs->get(node->ivex)->data);
      node = node->nextEdge;
    }
  }
}

bool ListDG::topologicalSort()
{
  Object_list_ptr tops = Object_list_ptr();
  return topologicalSort(tops);
}

/*
 * 拓扑排序
 *
 * 返回值：
 *     true 成功排序，并输入结果
 *     false 失败(该有向图是有环的)
 */
bool ListDG::topologicalSort(Object_list_ptr tops)
{
  int index = 0;
  int num = mVexs->size();
  int ins[num]; // 入度数组
  // Object_ptr [] tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。
  std::queue<int> queue; // 辅组队列

  // ins = new int[num];
  // tops  = new Object_ptr [num];
  // queue = new LinkedList<Integer>();

  // 统计每个顶点的入度数
  auto itm = mVexs->begin();
  for (int i = 0; i < num; i++)
  {
    std::advance(itm, i);
    ENode *node = (*itm)->firstEdge;
    while (node != NULL)
    {
      ins[node->ivex]++;
      node = node->nextEdge;
    }
  }

  // 将所有入度为0的顶点入队列
  for (int i = 0; i < num; i++)
  {
    if (ins[i] == 0)
    {
      queue.push(i); // 入队列
    }
  }

  auto it_tops = tops->begin();
  while (!queue.empty())
  {                        // 队列非空
    int j = queue.front(); // 出队列。j是顶点的序号
    queue.pop();
    std::advance(itm, j);
    std::advance(it_tops, index++);
    *it_tops = (*itm)->data;         // 将该顶点添加到tops中，tops是排序结果
    ENode *node = (*itm)->firstEdge; // 获取以该顶点为起点的出边队列

    // 将与"node"关联的节点的入度减1；
    // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
    while (node != NULL)
    {
      // 将节点(序号为node->ivex)的入度减1。
      ins[node->ivex]--;
      // 若节点的入度为0，则将其"入队列"
      if (ins[node->ivex] == 0)
      {
        queue.push(node->ivex); // 入队列
      }

      node = node->nextEdge;
    }
  }

  if (index != num)
  {
    return false;
  }

  return true;
}
